Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Free, publicly-accessible full text available September 30, 2024
-
Free, publicly-accessible full text available May 1, 2024
-
Abstract Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set
by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex$S \subset \mathbb {R}^k$ , whose geometric realization,$\Delta $ , is semialgebraically homeomorphic to$|\Delta |$ S . In this paper, we consider a weaker version of this question. We prove that for any , there exists an algorithm which takes as input a description of a semialgebraic subset$\ell \geq 0$ given by a quantifier-free first-order formula$S \subset \mathbb {R}^k$ in the language of the reals and produces as output a simplicial complex$\phi $ , whose geometric realization,$\Delta $ is$|\Delta |$ -equivalent to$\ell $ S . The complexity of our algorithm is bounded by , where$(sd)^{k^{O(\ell )}}$ s is the number of polynomials appearing in the formula , and$\phi $ d a bound on their degrees. For fixed , this bound is$\ell $ singly exponential ink . In particular, since -equivalence implies that the$\ell $ homotopy groups up to dimension of$\ell $ are isomorphic to those of$|\Delta |$ S , we obtain a reduction (having singly exponential complexity) of the problem of computing the first homotopy groups of$\ell $ S to the combinatorial problem of computing the first homotopy groups of a finite simplicial complex of size bounded by$\ell $ .$(sd)^{k^{O(\ell )}}$